from typing import List, Any, Iterator, Tuple, Dict
from collections import Iterable

class Graph(object):
    def __init__(self, edges):
        
        #存储顶点和边列表的邻接表
        self.adjList : Dict[Any,List[Any]] = dict()
        self.vertexes = set()
        #将edges 元组（adj_A, adj_B）表示的边, 拆解开添加到adjList中
        for (src, dst), weight in edges.items():
            # 将邻接表中的节点从 src 分配到 dest
            if src in self.adjList.keys():
                self.adjList[src].append((dst,weight))
            else:    
                self.adjList[src] = [(dst,weight)]
            self.vertexes.add(src)
            self.vertexes.add(dst)
            
        print(f" all vertexex of gragh : {self.vertexes}")
        
        self.node_input_nodes : Dict[Any ,List[Any]] = dict()
        #self.node_input_nodes = self.vertex_input_nodes()
        self.node_output_nodes : Dict[Any ,List[Any]] = dict()
        #self.node_output_nodes = self.vertex_output_nodes()
        
        self.node_input_digree : Dict[Any, int] = dict()
        #[self.node_input_digree.setdefault(u,len(item)) for u, item in self.node_input_nodes.items()]
        
        self.node_output_digree : Dict[Any, int] = dict()
        #[self.node_output_digree.setdefault(u,len(item)) for u, item in self.node_output_nodes.items()]
        
    def view(self):
        for src,dst_list in self.adjList.items():
            # 打印当前顶点及其所有相邻顶点
            for i, (dst,weight) in enumerate(dst_list):
                print(f'({src} —> {dst},{weight}) ', end='')
            print()

    def find_path(self, start_node, end_node) -> List[Any]:
        '''
        if start_node == end_node:
            return [start_node]
        path = [start_node]
        while start_node!= end_node:
            start_node = self.adjList[start_node][0]
        '''
        path : List[Any] = list()
        path.append(start_node)
        if (start_node == end_node):
            return path
        if start_node not in self.adjList.keys():
            return None
        
    def caculate_vertex_digree(self) -> Dict[Any,int]:
        in_degrees = dict((u,0) for u in self.vertexes)
        for src in self.vertexes:
            if src in self.adjList.keys():
                dst_list = self.adjList[src]         
                for (dst,weight) in dst_list:     
                    in_degrees[dst] += 1    #计算每个顶点的入度
                           
        return in_degrees
    
    def vertex_input_nodes(self) -> Dict[Any, List[Any]]:
        [self.node_input_nodes.setdefault(u, []) for u in self.vertexes]
        
        for src in self.vertexes:
            if src in self.adjList.keys():
                dst_list = self.adjList[src]         
                for (dst,weight) in dst_list: 
                    self.node_input_nodes.setdefault(dst, []).append(src)
        
        return self.node_input_nodes 
                     
    def vertex_output_nodes(self) -> Dict[Any, List[Any]]:
        [self.node_output_nodes.setdefault(u, []) for u in self.vertexes]
        for src in self.vertexes:
            if src in self.adjList.keys():
                dst_list = self.adjList[src]
                for (dst,weight) in dst_list:          
                    self.node_output_nodes.setdefault(src, []).append(dst)                   
        return self.node_output_nodes
     
    def top_sort(self) -> List[Any]:
        
        #self.node_input_digree = self.caculate_vertex_digree()  # or following method
        
        [self.node_input_digree.setdefault(u,len(item)) for u, item in self.node_input_nodes.items()]

        zero_digree_vertexes = [u for u in self.node_input_digree if self.node_input_digree[u] == 0]   # 筛选入度为0的顶点

        sort_seq = [] 
        while len(zero_digree_vertexes) > 0: 
            src = zero_digree_vertexes.pop()
            #print(src)
            sort_seq.append(src)
            if src in self.adjList.keys(): 
                for (dst,weight) in self.adjList[src]:    
                    self.node_input_digree[dst] -= 1    #移除其所有出边
                    if self.node_input_digree[dst] == 0:        
                        zero_digree_vertexes.append(dst)          #再次筛选入度为0的顶点            
        return sort_seq
                 
if __name__ == '__main__':
    edges_pairs = {(1,2) : 1,
                   (1,3) : 1,
                   (2,4) : 2,
                   (2,5) : 2, 
                   (3,4) : 3,
                   (4,5) : 4,
                   (4,6) : 2,
                   (6,5) : 2}
    graph = Graph(edges_pairs)
    graph.view()
    vertex_input_nodes = graph.vertex_input_nodes()
    sort_seq = graph.top_sort()
    print(sort_seq)
    for key, value in vertex_input_nodes.items():
        print(key, value)
    
    vertex_output_nodes = graph.vertex_output_nodes()
    for key, value in vertex_output_nodes.items():
        print(key, value)

